import java.util.*;

public class Test {
    /*
    题目1：前缀和
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), q = in.nextInt();

        int[] arr = new int[n + 1];
        for(int i = 1; i < n + 1; i++){
            arr[i] = in.nextInt();
        }

        long[] dp = new long[n + 1];
        for(int i = 1; i < n + 1; i++){
            dp[i] = dp[i - 1] + arr[i];
        }

        while(q > 0){
            int l = in.nextInt();
            int r = in.nextInt();
            System.out.println(dp[r] - dp[l - 1]);
            q--;

        }
    }

    /*
    题目2：二维前缀和
     */
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();

        int[][] arr = new int[n + 1][m + 1];
        for(int i = 1; i < n + 1; i++){
            for(int j = 1; j < m + 1; j++){
                arr[i][j] = in.nextInt();
            }
        }

        long[][] dp = new long[n + 1][m + 1];

        for(int i = 1; i < n + 1; i++){
            for(int j = 1; j < m + 1; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
            }
        }

        while(q > 0){
            int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
            System.out.println(dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]);
            q--;
        }
    }

    /*
    题目3：寻找数组的中心下标
     */
    public int pivotIndex(int[] nums) {
        int n = nums.length;

        int[] f = new int[n];
        int[] g = new int[n];

        for(int i = 1; i < n; i++){
            f[i] = f[i - 1] + nums[i - 1];
        }

        for(int i = n - 2; i >= 0; i--){
            g[i] = g[i + 1] + nums[i + 1];
        }

        for(int i = 0; i < n; i++){
            if(f[i] == g[i]){
                return i;
            }
        }
        return -1;
    }

    /*
    题目4：除自身以外数组的乘积
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;

        int[] f = new int[n];
        int[] g = new int[n];

        f[0] = 1;
        for(int i = 1; i < n; i++){
            f[i] = f[i - 1] * nums[i - 1];
        }

        g[n - 1] = 1;
        for(int i = n - 2; i >= 0; i--){
            g[i] = g[i + 1] * nums[i + 1];
        }

        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = f[i] * g[i];
        }
        return arr;
    }

    /*
    题目5：和为 k 的子数组
     */
    public int subarraySum(int[] nums, int k) {

        int sum = 0, ret = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        for(int x : nums){
            sum += x;
            ret += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return ret;
    }


}
